1. Field of the Invention
The present invention applies to the field of data coding and, in particular, to an encoder and a decoder.
2. Description of the Prior Art
Digital devices, such as computers and various digital communications equipment, store and process data as binary digits, also known as bits. A bit is either zero or one (0 or 1). All digital information, such as mp3 files, jpeg images, text files, DVD movies, and so on are stored as a collection of bits. When bits are transferred over a communication medium, errors may be introduced so that the bits received are not identical to the original bits. To ensure the accuracy of received data, various error detection and correction devices have been developed. A device that can detect an error can ask for retransmission. A device that can correct errors can perform correction on the received data.
These error detection and correction techniques include parity check codes, checksums, block codes such as Hamming codes, and cyclic redundancy checks. Using a Hamming encoder on a block of data bits produces a codeword that can be decoded to correct one error. Most Hamming encoders, and other linear block encoders, operate by generating parity bits over the block of data being encoded and adding the parity bits to the data block to create a codeword.
The codeword is then modulated and sent over a communications medium such as radio waves, optical fiber, coaxial cable, twisted pair wires, integrated circuit, or a computer bus. The received codeword may have an error in it. For example, if the sent codeword is “0011001” and the received codeword is “0001001,” then there is an error in position three (counting left to right). A decoder then generates a syndrome of the received codeword that can be used to locate an error in the received codeword. Hamming codes are well known, and discussions and examples can be found in many textbooks concerning Digital Communications.
When implemented in hardware, the encoder that generates the codeword and the decoder that corrects an error introduced during transmission have look-up tables that are used to generate the parity and syndrome bits and to map the syndrome to the location of the error. Such look-up tables add memory and complexity to the encoder and the decoder. Furthermore, some encoders are not pipelined, resulting in a need for rewriteable memory that adds complexity and cost to the hardware, and takes up valuable die area on a chip.